
#include "nester.h"

namespace Nesting
{
	Nester* Nester::instance_ = 0 ;
	
	Nester::Nester(const std::string& tile_filename)
	{
		std::srand(std::time(0));
		gx_assert(instance_ == 0) ;
		instance_ = this ;

		//cbox = new Rectangular_box("data/boundary/dighe1.line");

		// may throw Bad_input exception
		read_polygon_set(tile_filename, std::back_insert_iterator< std::vector<Nesting_polytope*> >(polytope_set), "txt");
		
		// calculate a reasonable bounding box size
		double max_width = std::numeric_limits<double>::lowest();
		total_volume = 0.0;
		max_volume = std::numeric_limits<double>::lowest();
		for (unsigned int i = 0; i < polytope_set.size(); i++)
		{
			if ( Nesting_polygon* np = dynamic_cast<Nesting_polygon*>(polytope_set[i]) )
			{
				CGAL::Iso_rectangle_2<K> bdbox = np->bbox();
				//avg_width += (bdbox.xmax() - bdbox.xmin);
				max_width = std::max(bdbox.xmax() - bdbox.xmin(), max_width);

				if (np->is_clockwise_oriented())
					np->reverse_orientation();

				int r = std::rand();
				if (r%2 == 0)
					np->rotate(180.0);
			}
			double vol = polytope_set[i]->volume();
			total_volume += vol;
			max_volume = std::max(max_volume, vol);
		}
		max_width *= 5.0;
		cbox = new Rectangular_box(0.0, 0.0, max_width, max_width*1.5);

		// initially distribute by bin packing
		// 2D case
		Bin_packing_2 bp(*static_cast<Rectangular_box*>(cbox));

		
		// random order
		//double max_height = std::numeric_limits<double>::min();
		//std::random_shuffle(polytope_set.begin(), polytope_set.end());
		//for (unsigned int i = 0; i < polytope_set.size(); i++)
		//{
		//	if ( Nesting_polygon* np = dynamic_cast<Nesting_polygon*>(polytope_set[i]) )
		//	{
		//		double x, y;
		//		if ( bp.put_one_bin(np->bbox(), x, y) )
		//		{
		//			np->translate(x, y);
		//		}
		//		CGAL::Iso_rectangle_2<K> bdbox = np->bbox();
		//		max_height = std::max(bdbox.ymax(), max_height);
		//	}
		//}

		// insert from large to small		
		std::priority_queue<Nesting_polytope*, std::vector<Nesting_polytope*>, area_cmp> np_queue;
		for (unsigned int i = 0; i < polytope_set.size(); i++)
			np_queue.push(polytope_set[i]);
		double max_height = std::numeric_limits<double>::lowest();
		while (!np_queue.empty())
		{
			Nesting_polytope *npp = np_queue.top();
			np_queue.pop();
			if ( Nesting_polygon* np = dynamic_cast<Nesting_polygon*>(npp) )
			{
				double x, y;
				if ( bp.put_one_bin(np->bbox(), x, y) )
				{
					np->translate(x, y);
				}
				CGAL::Iso_rectangle_2<K> bdbox = np->bbox();
				max_height = std::max(bdbox.ymax(), max_height);
			}
		}		
		cbox->lower(cbox->y_max() - max_height);
		std::cout<<"Utilization = "<< total_volume/cbox->volume()<< std::endl;
		
	}
	// 2D temporarily
	double Nester::local_search(unsigned int index, 
								const Vector_2& v,
								//double pre_obj_val,
								//double& obj_val,
								//double scale,
								const std::vector< std::vector<double> >& penalties, 
								std::vector< std::vector<double> >& miu,
								std::vector<unsigned int>& overlap_with,
								Nesting_polygon& res)
	{
		double lambda = 0.04 * max_volume;
		
		Nesting_polygon *np = dynamic_cast<Nesting_polygon*>(polytope_set[index]);
		// get the range of translation under this vector field, to ensure polygon is inside container
		double minx = cbox->x_min(), maxx = cbox->x_max();
		double miny = cbox->y_min(), maxy = cbox->y_max();
		double max_t = std::numeric_limits<double>::max();
		double min_t = std::numeric_limits<double>::lowest();

		// put outside the container first
		double oppo_max_t = 0.0;
		for (unsigned int i = 0; i < np->size(); i++)
		{
			if (v.x() > 0.0) // polygon intended to be moved to right
			{
				double t = (np->vertex(i).x() - minx)/v.x();
				oppo_max_t = std::max(oppo_max_t, t);
			}
			else if (v.x() < 0.0) // polygon intended to be moved to left
			{
				double t = (np->vertex(i).x() - maxx)/v.x();
				oppo_max_t = std::max(oppo_max_t, t);
			}
			if (v.y() > 0.0) // polygon intended to be moved to top
			{
				double t = (np->vertex(i).y() - miny)/v.y();
				oppo_max_t = std::max(oppo_max_t, t);
			}
			else if (v.y() < 0.0) // polygon intended to be moved to bottom
			{
				double t = (np->vertex(i).y() - maxy)/v.y();
				oppo_max_t = std::max(oppo_max_t, t);
			}
		}
		Overlap_2::Vector_2 oppo_v = -oppo_max_t * v;
		np->translate(oppo_v.x(), oppo_v.y());
		//glut_viewer_redraw();
		for (unsigned int i = 0; i < np->size(); i++)
		{
			if (v.x() > 0.0)
			{
				double t = (maxx - np->vertex(i).x())/v.x();
				max_t = std::min(t, max_t);
				t = (minx - np->vertex(i).x())/v.x();
				min_t = std::max(t, min_t);
			}
			if (v.x() < 0.0)
			{
				double t = (minx - np->vertex(i).x())/v.x();
				max_t = std::min(t, max_t);
				t = (maxx - np->vertex(i).x())/v.x();
				min_t = std::max(t, min_t);
			}
			if (v.y() > 0.0)
			{
				double t = (maxy - np->vertex(i).y())/v.y();
				max_t = std::min(t, max_t);
				t = (miny - np->vertex(i).y())/v.y();
				min_t = std::max(t, min_t);
			}
			if (v.y() < 0.0)
			{
				double t = (miny - np->vertex(i).y())/v.y();
				max_t = std::min(t, max_t);
				t = (maxy - np->vertex(i).y())/v.y();
				min_t = std::max(t, min_t);
			}
		}
		Overlap *overlap_sum = new Overlap_2;
		std::vector<Overlap*> all_overlaps;
		all_overlaps.reserve(polytope_set.size());
		std::vector<unsigned int> oidx;
		oidx.reserve(all_overlaps.size());
		for (unsigned int i = 0; i < polytope_set.size(); i++)
		{
			if (i == index)	continue;
			Nesting_polygon *mvp = dynamic_cast<Nesting_polygon*>(polytope_set[index]);
			Nesting_polygon *stp = dynamic_cast<Nesting_polygon*>(polytope_set[i]);
			Overlap *mutual_overlap = new Overlap_2(mvp, stp, v, lambda*penalties[index][i]);
			*overlap_sum += *mutual_overlap;
			all_overlaps.push_back(mutual_overlap);
			oidx.push_back(i);
			//miu[index][i] = miu[i][index] = 0.0;
			//delete mutual_overlap;
		}
		double min_overlap_t;
		overlap_sum->min(min_t, max_t, min_overlap_t);
		double overlap_area = overlap_sum->volume_at(min_overlap_t);

		np->translate(min_overlap_t*v.x(), min_overlap_t*v.y());
		res = *np;
		for (unsigned int i = 0; i < polytope_set.size(); i++)
			miu[i][index] = miu[index][i] = 0.0;
		// update miu values
		for (unsigned int i = 0; i < all_overlaps.size(); i++)
		{
			double vol = std::fabs(all_overlaps[i]->volume_at(min_overlap_t));
			//miu[oidx[i]] = vol/(1+penalties[index][oidx[i]]);
			//miu[oidx[i]] = vol;
			if (vol >= 1.0e-3)		
			{
				overlap_with.push_back(oidx[i]);
				miu[index][oidx[i]] = vol/(1+penalties[index][oidx[i]]);
				miu[oidx[i]][index] = miu[index][oidx[i]] ;
				//std::cout<<vol<<',';
			//	penalties[index][oidx[i]] += 1.0;
			//	penalties[oidx[i]][index] += 1.0;
			}
		}


		for (unsigned int i = 0; i < all_overlaps.size(); i++)
			delete all_overlaps[i];
		delete overlap_sum;
		//glut_viewer_redraw();
		return std::fabs(overlap_area);
	}
	void Nester::guided_local_search(unsigned int index)
	{
		static const double threshold = 1.0e-4;
		Nesting_polygon *np = dynamic_cast<Nesting_polygon*>(polytope_set[index]);
		std::cout<<"\nStart looking for minimal overlap...\n";	
	
		//std::cout<<"\nPolytope "<<index<<' ';
		//Vector_2 search_dir[] = {Vector_2(0.0, -1.0), Vector_2(-1.0, 0.0), Vector_2(0.0, 1.0), Vector_2(1.0, 0.0)};
		Vector_2 search_dir[][4] = {{Vector_2(0.0, -1.0), Vector_2(-1.0, 0.0), Vector_2(0.0, 1.0), Vector_2(1.0, 0.0)},
									{Vector_2(1.0, 0.0), Vector_2(0.0, -1.0), Vector_2(-1.0, 0.0), Vector_2(0.0, 1.0)}};
		//std::vector<int> dir_select(8, 0);
		//for (unsigned int i = 0; i < dir_select.size(); i++)
		//	dir_select[i] = i;
		std::vector< std::vector<double> > p(polytope_set.size());
		for (unsigned int i = 0; i < p.size(); i++)
			p[i].assign(polytope_set.size(), 0.0);
		//std::for_each(p.begin(), p.end(), std::bind2nd(std::mem_fun_ref(&std::vector<double>::resize), polytope_set.size() - 1));
		std::vector< std::vector<double> > miu(polytope_set.size());
		for (unsigned int i = 0; i < miu.size(); i++)
			miu[i].assign(polytope_set.size(), 0.0);

		std::queue<unsigned int> to_be_moved;
		to_be_moved.push(index);
		std::set<unsigned int> in_queue;
		in_queue.insert(index);
		//double scale = max_volume;
		const int n = 4;
		while (!to_be_moved.empty())
		{
			unsigned int idx = to_be_moved.front();
			to_be_moved.pop();
			in_queue.erase(idx);
			//double overlap_area = -1.0;
			double overlap_area[n];
			//double pre_obj_val, obj_val = std::numeric_limits<double>::max();
			//double pre_overlap_area;
			int i;		
			std::vector<unsigned int> overlap_with[n];
			Nesting_polygon backup[n];
			for (i = 0; i < n; i++)
			{
				// only consider the ones that overlap in the last try
				//overlap_with.clear();
				overlap_area[i] = local_search(idx, search_dir[0][i%4],  p, miu, overlap_with[i], backup[i]);

				//std::cout<<overlap_area[i]<<", ";
				if (overlap_area[i] <= threshold)	 break; 

				// look for the maximum miu
				double max_miu = -1.0;
				//unsigned int r, c;
				//for (unsigned int k = 0; k < miu.size(); k++)
				//{
				//	std::vector<double>::iterator it = std::max_element(miu[k].begin(), miu[k].end());
				//	if ( max_miu < *it)
				//	{
				//		r = k;
				//		c = it - miu[k].begin();
				//		max_miu = *it;
				//	}
				//}
				//p[r][c] += 1.0;
				//p[c][r] += 1.0;
				unsigned int c;
				for (unsigned int k = 0; k < miu[idx].size(); k++)
					if (miu[idx].at(k) > max_miu)
					{
						max_miu = miu[idx].at(k);
						c = k;
					}
				p[idx][c] += 2.0;
				p[c][idx] += 2.0;
				//if (overlap_area == pre_overlap_area)
				//{
				//	i = 4; 
				//	break;
				//}
				//std::cout << "overlap_area = " << overlap_area<<',';
				//std::cout << "obj_val = " << obj_val<<',';
				//std::cout << "p["<<r<<"]["<<c<<"] = "<<p[r][c]<<", ";
				//std::cout << "p["<<c<<"]["<<r<<"] = "<<p[c][r]<<"\n";
			}
			if (i == n)
			{
				//std::cout<<"\nCannot find. Move overlapped polygons...\n";
				//for (unsigned int j = 0; j < overlap_with.size(); j++)
				//{
				//	std::set<unsigned int>::iterator it = in_queue.find(overlap_with[j]);
				//	if (it == in_queue.end())
				//	{
				//		to_be_moved.push(overlap_with[j]);
				//		in_queue.insert(overlap_with[j]);
				//	}
				//}
				unsigned int min_idx = std::min_element(overlap_area, overlap_area+n) - overlap_area;
				for (unsigned int j = 0; j < overlap_with[min_idx].size(); j++)
				{
					std::set<unsigned int>::iterator it = in_queue.find(overlap_with[min_idx][j]);
					if (it == in_queue.end())
					{
						to_be_moved.push(overlap_with[min_idx][j]);
						in_queue.insert(overlap_with[min_idx][j]);
					}
				}
				*dynamic_cast<Nesting_polygon*>(polytope_set[idx]) = backup[min_idx];
				//std::cout << "  Use the "<<min_idx<<"th move";
			}
			//std::cout<<std::endl;
		}
		std::cout<<"\nSearching ends.\n";
	}
	void Nester::find_nonoverlap_pos()
	{
		//static const int N = 5;
		//static const double threshold = 1.0e-4;
		//std::cout<<"Start looking for minimal overlap...\n";
		// find which polytopes are outside container
		unsigned int i = 0;
		for (; i < polytope_set.size(); i++)
		{
			if (!cbox->bounded_side(*polytope_set[i]))
			{
				//std::cout<<"Polytope "<<i<<' ';
				if ( Nesting_polygon *np = dynamic_cast<Nesting_polygon*>(polytope_set[i]) )
				{
					guided_local_search(i);
				}
				// else if this is a polyhedron
			}// !cbox->bounded_side(*polytope_set[i])
		}
		//std::cout<<"Searching ends.\n";
		// utilization
		std::cout<<"Utilization = "<<total_volume/cbox->volume();
	}

	Nester::~Nester() 
	{
		for (unsigned int i = 0; i < polytope_set.size(); i++)
			delete polytope_set[i];
		polytope_set.clear();
		instance_ = 0 ; 
	}
	
	void Nester::shrink_bdbox(double f)
	{
		cbox->shrink(f);
	}
	void Nester::get_bbox(real& x_min, real& y_min, real& z_min, real& x_max, real& y_max, real& z_max)
	{
		x_min = cbox->x_min(); x_max = cbox->x_max();
		y_min = cbox->y_min(); y_max = cbox->y_max();
		z_min = cbox->z_min(); z_max = cbox->z_max();
	}
}
